class Solution(object):
    def numTrees(self, n):
        """
        :type n: int
        :rtype: int
        """
        dp = [1 for _ in range(n+1)]
        for l in range(2, n+1):
            num = 0
            for pivot in range(0, l):
                num += dp[pivot] * dp[l-1-pivot]
            dp[l] = num
        return dp[-1]

print(Solution().numTrees(0))